package com.example.tree.bst;

import com.example.tree.TreeNode;

/**
 * 实现一个函数，检查一棵二叉树是否为二叉搜索树
 */
public class Interview04_05_IsValidBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(6);

        System.out.println(isValidBST(root));

    }

    /**
     * 中序遍历一棵树，返回该树是否是BST
     * @param root
     * @return
     */
    public static boolean isValidBST(TreeNode root) {
        State state = new State();
        isValidBSTByInorder(root, state);
        return state.isBST;
    }

    private static void isValidBSTByInorder(TreeNode root, State state) {
        if (root == null) {
            state.isBST = true;
            return;
        }

        isValidBSTByInorder(root.left, state);

        if ((root.val <= state.preNodeVal) || !state.isBST){// 如果序列非递增or左子树不是BST,该树不是BST
            state.isBST = false;
            return;
        }
        // 当前子树是BST
        state.isBST = true; // 更新状态
        state.preNodeVal = root.val;// 更新preNodeVal值

        isValidBSTByInorder(root.right, state);

    }


    private static class State {
        boolean isBST = false;
        long preNodeVal = Long.MIN_VALUE; // 用于记录前一个节点的val值
    }
}
